package com.chapter2.sort;

/** 
 * @ClassName: MergeSortUp2Down 
 * @Description: 归并排序(自顶向下)--自顶向下与自底向上时间复杂度均为O(NlgN)，但是在自底向上在对链表排序会有优势
 * 归并排序非常稳定，最好最坏平均情况时间复杂度均为O(NlgN)，而且这是排序算法的极致，是非常好的一个排序选择。在速度方面归并排序无可挑剔，但是在对内存利用上面，是他的弊端。
 * 因为归并排序 需要两倍的内存空间才能完成排序（当然可以利用一种方法来优化，不过那会使得代码非常繁杂，那是专家该做的事）
 * @author minjun minjun@bw30.com
 * @date 2015-2-13 下午11:14:40 
 *  
 */
public class MergeSortUp2Down extends AbstractSort{
	
	private int[] aux;

	@Override
	public void sort(int[] a) {
		int len=a.length;
		aux=new int[len];
		sort(a,0,len-1);
	}
	
	/**
	 * 
	* @Title: sort 
	* @Description: 递归排序
	* @param @param a
	* @param @param start
	* @param @param end    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	private void sort(int[] a, int start, int end) {
		//给出结束递归的条件
		if(start>=end) return;
		//找到中间点，拆分成两半
		int mid=(start+end)/2;
		//左半边排序
		sort(a, start, mid);
		//右半边排序
		sort(a,mid+1,end);
		//合并（其实排序的操作是在合并里面进行的）
		merge(a, start, mid, end);
	}


	/**
	 * 
	* @Title: merge 
	* @Description: 合并 
	* @param @param a
	* @param @param start
	* @param @param mid
	* @param @param end    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	public void merge(int[] a,int start,int mid,int end){
		for(int k=start;k<=end;k++) aux[k]=a[k];
		int i=start;
		int j=mid+1;
		for(int k=start;k<=end;k++){
			if(i>mid) 						a[k]=aux[j++];//如果左边部分都已经排序到原始数组里面，那么只剩下右边，直接添加到原始数组后面即可
			else if(j>end) 					a[k]=aux[i++];//与上相反
			else if(less(aux[j], aux[i])) 	a[k]=aux[j++];//如果左边比较小，那么将左边的添加到原始数组左起位置
			else 							a[k]=aux[i++];//如果右边的比较小，那么僵右边的添加到原始数组左起位置
		}
	}
}
